// https://www.lintcode.com/problem/next-permutation/description

class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: A list of integers
     */
    vector<int> nextPermutation(vector<int> &nums) {
        int* array = new int[nums.size()];
        memcpy(array, &nums[0], nums.size() * sizeof(int));
        next_permutation(nums.begin(), nums.end());
        return nums;
    }
};

// https://www.lintcode.com/problem/52/
class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: A list of integers
     */
    vector<int> nextPermutation(vector<int> &nums) {
        int n = nums.size();
        for (int i = n - 1; i >= 0; --i) { // 倒序遍历
            if (i > 0 && nums[i] > nums[i - 1]) { // 找到第一个数值变小的点，这样代表右边有大的可以和它换，而且可以保证是next permutation
                for (int j = n - 1; j > i - 1; --j) { // 找到后再次倒序遍历
                    if (nums[j] > nums[i - 1]) { // 找到第一个比刚才那个数值大的点，互相交换
                        swap(nums[j], nums[i - 1]);
                        // 因为之前保证了，右边这段数从右到左是一直变大的，所以直接双指针reverse
                        int low = i, high = nums.size() - 1;
                        while (low < high) {
                            swap(nums[low++], nums[high--]);
                        }
                        return nums;
                    }
                }
            }
        }
        // 如果循环结束了，表示没找到能替换的数，表示序列已经是最大的了
        reverse(nums.begin(), nums.end());
        return nums;
    }
};